package summary;

import java.util.*;

/**
 * @Author: 海琳琦
 * @Date: 2022/7/10 17:32
 */
public class Title126II {

    public static List<List<String>> findLadders(String beginWord, String endWord, List<String> wordList) {
        List<List<String>> result = new ArrayList<>();
        //加快搜索速度
        Set<String> wordLists = new HashSet<>();
        wordLists.addAll(wordList);
        if (!wordLists.contains(endWord)){
            return result;
        }
        //BFS队列
        LinkedList<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        //构建图
        Map<String, List<String>> pathGraph = new HashMap<>();
        //记录节点层数
        Map<String, Integer> levelGraph = new HashMap<>();
        levelGraph.put(beginWord, 0);
        int step = 1;
        boolean flag = false;
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i++) {
                String word = queue.poll();
                for (int j = 0; j < word.length(); j++) {
                    char[] chars = word.toCharArray();
                    //单个位置 替换单词
                    for (char k = 'a'; k <= 'z'; k++) {
                        if (chars[j] != k) {
                            chars[j] = k;
                            String newWord = String.valueOf(chars);
                            //如果构造的单词 在 单词集合中没有 continue
                            if (!wordLists.contains(newWord)) {
                                continue;
                            }
                            //bfs最短路径
                            if (levelGraph.containsKey(newWord)) {
                                //同一层多条路径时   构造图关系
                                if(levelGraph.get(newWord) == step){
                                    pathGraph.get(newWord).add(word);
                                }
                                continue;
                            }
                            //记录节点位置
                            levelGraph.put(newWord, step);
                            //word - newWord
                            pathGraph.computeIfAbsent(newWord, q -> new ArrayList<>()).add(word);
                            queue.offer(newWord);
                            if (newWord.equals(endWord)) {
                                flag = true;
                            }
                        }
                    }
                }
            }
            step++;
            if (flag) {
                break;
            }
        }
        if (flag) {
            LinkedList<String> list = new LinkedList<>();
            list.offer(endWord);
            dfs(pathGraph, list, result, endWord, beginWord);
        }
        return result;
    }

    private static void dfs(Map<String, List<String>> pathGraph, LinkedList<String> list, List<List<String>> result, String cur, String endWord) {
        if (cur.equals(endWord)) {
            result.add(new ArrayList<>(list));
            return;
        }
        for (String node : pathGraph.get(cur)) {
            list.addFirst(node);
            dfs(pathGraph, list, result, node, endWord);
            list.removeFirst();
        }
    }

    public static void main(String[] args) {
        String beginWord = "hit";
        String endWord = "cog";
        List<String> wordList = Arrays.asList("hot", "dot", "dog", "lot", "log", "cog");
        findLadders(beginWord, endWord, wordList);
    }
}
